package com.heima.datastructure.redblacktree;

/**
 * <h2><strong>红黑树</strong></h2>
 * <p><strong>红黑树也是一种自平衡的二叉搜索树，较于AVL树，插入删除时旋转次数更少</strong></p>
 * <ul>
 *     <li><strong>红黑树特性
 *          <ol>
 *              <li>所有节点都有两种颜色：红、黑</li>
 *              <li>根节点是黑色</li>
 *              <li>叶子节点（外部节点，空节点）都是黑色
 *                  <ul>
 *                      <li>这里的叶子节点指的是所有的null，每个null都要画出来</li>
 *                      <li>红黑树中一个节点的左右孩子都为null，不将其看作叶子节点</li>
 *                      <li>红黑树的叶子节点包括最底层的null节点（外部节点）以及内部缺失的节点（空节点）</li>
 *                  </ul>
 *              </li>
 *              <li>红色节点的子节点都是黑色
 *                  <ul>
 *                      <li>红色节点的父节点都是黑色</li>
 *                      <li>从根节点到任意一个红黑树的叶子节点的路径上不能有两个连续的相邻的红色节点</li>
 *                  </ul>
 *              </li>
 *              <li>从根节点到任意一个叶子节点，路径途中的黑色节点个数一样
 *                  <ul>
 *                      <li>取当前树的任意子树的根节点，该根节点到该子树的叶子节点路径的黑色节点个数一样</li>
 *                      <li>所以任意节点到它所能到的叶子节点的路径中的黑色节点个数一样</li>
 *                  </ul>
 *              </li>
 *          </ol>
 *     </strong></li>
 * </ul>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/14 17:45
 */
public class RedBlackTree<K extends Comparable<K>, V> {

    private RBTNode<K, V> root; // 红黑树的根节点

    /**
     * 无参构造，root初始化默认就是null
     */
    public RedBlackTree() {
    }

    /**
     * 测试用，范围是当前包，传入一个正确的红黑树（为了测试指定树），进行插入删除
     *
     * @param root 红黑树的根节点
     */
    RedBlackTree(RBTNode<K, V> root) {
        this.root = root;
    }

    /**
     * 颜色枚举，红色和黑色
     */
    enum Color { // 范围当前包
        RED,
        BLACK
    }

    /**
     * 红黑树节点类
     *
     * @param <K> 节点类的key的数据类型
     * @param <V> 节点类的value的数据类型
     */
    static class RBTNode<K, V> { // 范围当前包
        K key; // key
        V value; // value
        RBTNode<K, V> left; // 左子节点
        RBTNode<K, V> right; // 右子节点
        RBTNode<K, V> parent; // 父节点
        Color color = Color.RED; // 颜色，只有红和黑

        // 判断当前节点是否是左孩子

        /**
         * 判断当前节点是否是左孩子
         *
         * @return 是左孩子返回true
         */
        boolean isLeftChild() { // 因为类的范围是当前包，所以其方法也设为当前包，设置为public多余了
            return parent != null && parent.right != this;
        }

        // 找到祖父节点

        /**
         * 找到祖父节点
         *
         * @return 祖父节点，有可能是null
         */
        RBTNode<K, V> grandparent() {
            RBTNode<K, V> parent = this.parent;
            if (parent == null) {
                return null; // 返回null虽然逻辑上有重叠，但是fix修正的时候前两种情况会跳过，不会使用grandparent的虚假值null（不可能存在）
            }
            return parent.parent;
        }

        // 找到叔叔节点，叔叔节点就是与父节点同级的节点

        /**
         * 找到当前节点的叔叔节点
         *
         * @return 叔叔节点，没有则返回null
         */
        RBTNode<K, V> uncle() {
            if (parent == null || parent.parent == null) {
                return null; // 返回null虽然逻辑上有重叠，但是fix修正的时候前两种情况会跳过，不会使用uncle的虚假值null（不可能存在）
            }
            return parent.isLeftChild() ? parent.parent.right : parent.parent.left;
        }

        // 找到兄弟节点

        /**
         * 找到兄弟节点
         *
         * @return 兄弟节点，没有则返回null
         */
        RBTNode<K, V> sibling() {
            if (parent == null) {
                return null;
            }
            return this.isLeftChild() ? parent.right : parent.left;
        }

        public RBTNode(K key) {
            this.key = key;
        }

        // 当前包才能用这个构造器，parent指针也不用初始化了，因为不会影响树，减负
        RBTNode(K key, V value, RBTNode<K, V> left, RBTNode<K, V> right, Color color) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
        }

        public RBTNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 判断一个节点是否是红色节点
     *
     * @param node 节点
     * @return 是红色节点则返回true
     */
    private boolean isRed(RBTNode<K, V> node) {
        return node != null && node.color == Color.RED;
    }

    /**
     * 判断一个节点是否是黑色节点
     *
     * @param node 节点
     * @return 是黑色节点，返回true
     */
    private boolean isBlack(RBTNode<K, V> node) {
        // return !isRed(node);
        return node == null || node.color == Color.BLACK;
    }

    /**
     * 右旋，对一个棵树做一次右旋操作，核心节点只包括根节点root、root.left、root.left.right
     * <p><strong>返回值为void是因为在右旋操作里面就要处理好与上层树之间的关系</strong></p>
     *
     * @param root 当前树的根节点
     */
    private void rightRotate(RBTNode<K, V> root) {
        RBTNode<K, V> parent = root.parent; // 记录根节点的父节点，后面更新当前树与更上级的树之间的关系
        // 1、旋转，这里是右旋，也就是根节点下来，根节点的左孩子上去，左孩子的右子树接到root的左子树，再将root接到左孩子的右子树上
        RBTNode<K, V> left = root.left; // 左孩子
        RBTNode<K, V> lRight = left.right; // 左孩子的右子树
        root.left = lRight; // 左孩子的右子树接到根节点的左孩子
        left.right = root; // 根节点的树接到左孩子的右子树
        // 2、更新父节点
        left.parent = parent; // 左孩子的父节点更新为根节点的父节点
        root.parent = left; // 根节点的父节点更新为左孩子
        if (lRight != null) {
            lRight.parent = root; // 如果左孩子有右子树，则更新右子树的根节点的父节点为root节点
        }
        // 3、更新和上层树之间的关系
        if (parent == null) { // root的父节点为null，说明没有更上层的树
            this.root = left; // 更新整棵树的根节点
        } else if (parent.left == root) {
            parent.left = left;
        } else {
            parent.right = left;
        }
    }

    /**
     * 左旋，对一棵树做一次左旋操作，核心节点只包括根节点root、root.right、root.right.left
     * <p><strong>返回值为void是因为在右旋操作里面就要处理好与上层树之间的关系</strong></p>
     *
     * @param root 当前树的根节点
     */
    private void leftRotate(RBTNode<K, V> root) {
        RBTNode<K, V> parent = root.parent;
        // 1、左旋操作
        RBTNode<K, V> right = root.right;
        RBTNode<K, V> rLeft = right.left;
        root.right = rLeft;
        right.left = root;
        // 2、修改parent指针
        root.parent = right;
        right.parent = parent;
        if (rLeft != null) {
            rLeft.parent = root;
        }
        // 3、处理与上层树之间的关系
        if (parent == null) {
            this.root = right;
        } else if (parent.left == root) {
            parent.left = right;
        } else {
            parent.right = right;
        }
    }

    /**
     * 判断当前红黑树和另一颗红黑树是否是同一棵树
     *
     * @param tree 另一颗红黑树
     * @return 一样返回true
     */
    public boolean isSameTree(RedBlackTree<K, V> tree) {
        return isSameTree(this.root, tree.root);
    }

    /**
     * 判断当前树和另一棵树是否为同一棵树，参数传的是根节点，范围是当前包，测试用
     *
     * @param root 树的根节点
     * @return 相同返回true
     */
    boolean isSameTree(RBTNode<K, V> root) {
        return isSameTree(this.root, root);
    }

    /**
     * 判断两颗红黑树是否相同，parent指针不放入考虑范围
     *
     * @param root1 红黑树1
     * @param root2 红黑树2
     * @return 相同返回true
     */
    private boolean isSameTree(RBTNode<K, V> root1, RBTNode<K, V> root2) {
        if (root1 == null && root2 == null) {
            return true;
        } else if (root1 == null || root2 == null) {
            return false;
        } else {
            if (root1.key.compareTo(root2.key) == 0) {
                if (root1.value.equals(root2.value)) {
                    if (root1.color.equals(root2.color)) {
                        // 这里没有将parent放入考虑范围，parent本来也是为了旋转时方便一些，去掉parent对树也没有影响
                        return isSameTree(root1.left, root2.left) && isSameTree(root2.right, root2.right);
                    }
                    return false;
                }
                return false;
            }
            return false;
        }
    }

    /**
     * 插入操作，默认插入节点为红色，插入后再进行平衡调整
     *
     * @param key   key
     * @param value value
     */
    public void put(K key, V value) {
        RBTNode<K, V> curr = root;
        RBTNode<K, V> parent = null;
        while (curr != null) {
            parent = curr;
            if (key.compareTo(curr.key) < 0) {
                curr = curr.left;
            } else if (curr.key.compareTo(key) < 0) {
                curr = curr.right;
            } else {
                curr.value = value;
                return; // 只用修改值，树的结构平衡没有被打破
            }
        }
        RBTNode<K, V> inserted = new RBTNode<>(key, value);
        if (parent == null) {
            root = inserted;
        } else if (key.compareTo(parent.key) < 0) {
            parent.left = inserted;
        } else {
            parent.right = inserted;
        }
        inserted.parent = parent; // 父指针
        fixInsertedRed(inserted);
    }

    /**
     * 修正插入红色节点后不平衡的情况，插入节点默认都是红色
     *
     * @param inserted 插入节点
     */
    private void fixInsertedRed(RBTNode<K, V> inserted) {
        RBTNode<K, V> parent = inserted.parent;
        RBTNode<K, V> uncle = inserted.uncle();
        RBTNode<K, V> grandparent = inserted.grandparent();
        // 1、inserted插入后是根节点，要把颜色修改为黑色
        if (parent == null) { // uncle不存在并且grandparent也不存在，会在这里跳过，不用这俩的虚假值null（应该是不存在的）
            inserted.color = Color.BLACK;
        }
        // 2、inserted插入后的父节点是黑色节点，那么一来没出现相邻情况，二来到每个叶子节点的黑色节点数不会改变。所以这种情况啥也不用干
        else if (isBlack(parent)) { // uncle不存在并且grandparent也不存在，会在这里跳过，不用这俩的虚假值null（应该是不存在的）
            return;
        }
        // 3、inserted插入后的父节点是红色节点，并且叔叔也是红色节点，则将父节点和叔叔节点变为黑色，将祖父节点变为红色，但是祖父节点的父亲、叔叔、祖父情况未知，有可能引发红红相邻，则把祖父节点当成插入节点，继续递归
        else if (isRed(parent) && isRed(uncle)) {
            parent.color = Color.BLACK; // parent变成黑色
            uncle.color = Color.BLACK; // uncle变成黑色
            grandparent.color = Color.RED; // grandparent变成红色
            fixInsertedRed(grandparent); // 递归处理祖父节点
            return;
        }
        // 4、inserted插入后的父节点是红色节点，并且叔叔是黑色节点，直接变色不可行，因为父节点变为黑色，叔叔节点本来就是黑色，祖父节点分叉的两边肯定不平衡，所以需要旋转
        else { // 上面的else已经除开了父节点为null、父节点黑色、父节点为红色并且叔叔节点为红色。所以这些全部取反就是父节点不可能为空并且父节点是红色，并且父节点和叔叔节点有一个为红色 => 父节点为红色，叔叔节点为黑色，要保证祖父节点到其为根节点的子树的叶子节点路径的黑色节点个数一样，则叔叔节点必定是null
            // 1、父亲为左孩子，插入节点也是左孩子，此时是LL不平衡，来一次右旋
            if (parent.isLeftChild() && inserted.isLeftChild()) { // 父节点是左孩子，并且父节点还是红色的，并且叔叔节点是黑色的，并且祖父节点只能是黑色，要想插入之前就是平衡的，那么叔叔节点只能是null节点，从分叉点（子树根节点）到任意叶子节点路径的黑色节点数一致
                // 将父节点变成黑色，旋转上去顶替原来祖父节点的位置，要保证平衡所以要设置为黑色
                parent.color = Color.BLACK;
                // 将祖父节点变成红色，旋转下来接到父节点的右孩子，uncle节点又只能是null，保证平衡就设置为红色
                grandparent.color = Color.RED;
                // 右旋
                rightRotate(grandparent); // 旋转后：父（父节点）：黑， 左（插入节点）：红， 右（祖父节点）：红
            }
            // 2、父亲为左孩子，插入节点是右孩子，此时是LR不平衡，来一次左右旋
            else if (parent.isLeftChild() && !inserted.isLeftChild()) {
                // 先来一次左旋变成LL情况
                leftRotate(parent);
                // 左旋后插入节点变成了父节点，原来的父节点变成了子节点，所以要旋转上去的是插入节点，要设置为黑色顶替祖父节点的位置
                inserted.color = Color.BLACK;
                // 祖父节点设置为红色，接到父节点的右子树（肯定是null）并修改颜色为红色
                grandparent.color = Color.RED;
                // 右旋
                rightRotate(grandparent); // 旋转后：父（插入节点）：黑， 左（父节点）：红， 右（祖父节点）：红
            }
            // 3、父亲为右孩子，插入节点是左孩子，此时是RL不平衡，来一次右左旋，同理，父节点为红色，祖父节点必为黑色，叔叔节点为黑色，要想保证平衡，也就是祖父节点到其为根节点的树的任意叶子节点的黑色节点一致，那么叔叔节点必定为null
            else if (!parent.isLeftChild() && inserted.isLeftChild()) {
                // 先来一次右旋变成RR情况
                rightRotate(parent);
                // 右旋后插入节点变成了父节点，原来的父节点变成了子节点，则将现在的父节点旋转上去顶替原来祖父节点的位置
                inserted.color = Color.BLACK;
                // 祖父节点旋转下来，接到现在的父节点的左子树（肯定是null）并修改颜色为红色
                grandparent.color = Color.RED;
                // 左旋
                leftRotate(grandparent); // 旋转后：父（插入节点）：黑， 左（祖父节点）：红， 右（父节点）：红
            }
            // 4、父亲为右孩子，插入节点也是右孩子，此时是RR不平衡，来一次左旋
            else {
                // 父节点旋转上去顶替原来祖父节点的位置，所以颜色也要改成黑色，保持平衡
                parent.color = Color.BLACK;
                // 祖父节点旋转下来，接到父节点的左孩子（肯定是null）并修改颜色为红色
                grandparent.color = Color.RED;
                // 左旋
                leftRotate(grandparent); // 旋转后：父（父节点）：黑， 左（祖父节点）：红， 右（插入节点）：红
            }
        }
    }

    /**
     * 删除节点
     * @param key key
     * @return 删除节点的value
     */
    public V remove(K key) {
        // 找到删除节点
        RBTNode<K, V> deleted = find(key);
        // 删除节点没找到
        if (deleted == null) {
            return null;
        }
        remove(deleted);
        return deleted.value;
    }

    /**
     * 删除节点，并修正
     * @param deleted 待删除节点
     */
    private void remove(RBTNode<K,V> deleted){
        RBTNode<K, V> parent = deleted.parent;
        // 找到删剩余的节点重组成新树的根节点
        RBTNode<K, V> remainRoot = remainRoot(deleted);
        // 删除节点没有子树
        if (remainRoot == null){
            // case 1: 如果删除节点是根节点
            if (deleted == root){
                root = null;
            }
            // case 2: 删除节点不是根节点
            else {
                if (isBlack(deleted)){
                    // 复杂处理，平衡调整，删除的和剩余形成树的根节点都为黑：双黑
                    fixDoubleBlack(deleted); // 没有左右孩子要删之前修正
                }
                // 红色叶子，不需要任何处理
                shift(parent, deleted, null);
                deleted.parent = null; // 垃圾回收
            }
            return;
        }
        // 删除节点有一个子树
        else if (deleted.left == null || deleted.right == null) {
            // case 1: 如果删除节点是根节点
            if (deleted == root){
                // 根节点是黑色，一个子树为null，则另一个子树必定为一个红色节点
                deleted.key = remainRoot.key;
                deleted.value = remainRoot.value;
                deleted.right = deleted.left = null; // 没有节点指向remainRoot会自动垃圾回收
                deleted.parent = null; // 垃圾回收
            }
            // case 2: 删除节点不是根节点
            else {
                shift(parent, deleted, remainRoot);
                deleted.parent = deleted.left = deleted.right = null; // 垃圾回收
                if (isBlack(deleted) && isBlack(remainRoot)){ // 双黑
                    // 复杂处理
                    fixDoubleBlack(remainRoot); // 有一个孩子要删完后修正
                }else{
                    remainRoot.color = Color.BLACK; // 有一个为黑色，哪怕删了一个，补回来就是了
                }
            }
            return;
        }
        // 删除节点有两个子树
        else {
            swap(deleted, remainRoot);
            // 转化成删除节点有一个子树或者没有
            remove(remainRoot);
        }
    }

    /**
     * 找到指定key的红黑树节点
     *
     * @param key key
     * @return 红黑树节点
     */
    private RBTNode<K, V> find(K key) {
        RBTNode<K, V> curr = root;
        while (curr != null) {
            if (key.compareTo(curr.key) < 0) {
                curr = curr.left;
            } else if (curr.key.compareTo(key) < 0) {
                curr = curr.right;
            } else {
                return curr;
            }
        }
        return null;
    }

    /**
     * 找到删除一个节点后，也就是在以删除节点为根节点的子树中删除根节点，剩下的节点重构变成一颗新树，返回新树的根节点
     *
     * @param deleted 删除节点
     * @return 新树的根节点
     */
    private RBTNode<K, V> remainRoot(RBTNode<K, V> deleted) {
        // 当删除节点找到的时候才会来找删剩下的这些节点组成的新树的根节点，所以deleted不可能为null
        if (deleted.left == null) {
            // 删除节点左子树是null，右子树都有可能，返回右子树，两种情况二合一
            return deleted.right;
        } else if (deleted.right == null) {
            // 删除节点右子树是null，左子树不为null，返回左子树
            return deleted.left;
        } else {
            // 删除节点左右子树都有，返回删除节点的后继节点
            RBTNode<K, V> successor = deleted.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            return successor;
        }
    }

    /**
     * 交换两个节点的key、value值，李代桃僵的思想，只交换值而不破坏结构，修改内部一些值去充当另一个节点
     *
     * @param node1 节点1
     * @param node2 节点2
     */
    private void swap(RBTNode<K, V> node1, RBTNode<K, V> node2) {
        K keyTemp = node1.key;
        V valueTemp = node1.value;
        node1.key = node2.key;
        node1.value = node2.value;
        node2.key = keyTemp;
        node2.value = valueTemp;
    }

    /**
     * 托孤方法
     * @param parent 托孤给谁
     * @param deleted 被删除节点
     * @param child 需要托孤的节点
     */
    private void shift(RBTNode<K,V> parent, RBTNode<K,V> deleted, RBTNode<K,V> child){
        if (parent == null){
            root = child;
        } else if (deleted.isLeftChild()) {
            parent.left = child;
        } else {
            parent.right = child;
        }
        if (child != null) {
            child.parent = parent;
        }
    }

    /**
     * 修正双黑
     * @param node 修正节点
     */
    private void fixDoubleBlack(RBTNode<K,V> node){
        if (node == root){
            return;
        }
        RBTNode<K, V> parent = node.parent;
        RBTNode<K, V> sibling = node.sibling();
        // case 3: 待调整节点是黑色，兄弟节点是红色，那么兄弟节点的孩子一定是黑色
        if (isRed(sibling)) {
            if (node.isLeftChild()){ // 待调整节点是左孩子
                leftRotate(parent); // 来一次左旋，将兄弟节点的左孩子变成新的兄弟节点，就变成了情况四：待调整节点兄弟是黑色，两个侄子也为黑色（null）
            } else { // 待调整节点是右孩子
                rightRotate(parent); // 来一次右旋，将兄弟节点的右孩子变成新的兄弟节点，就变成了情况四：待调整节点兄弟是黑色，两个侄子也为黑色（null）
            }
            // 这里有点复杂，两种情况：删除节点有一个孩子、没有孩子，分别讨论，可以发现，这样做都能实现待调整节点的兄弟节点变成黑色节点，进入情况四
            // 1、删除节点没有孩子： (传入参数修正时删除节点还没有被删除，此时的待调整节点就是待删除节点)
            //                           p(b)                                       s(r)                     s(b)
            //                          /    \                                     /    \                   /    \
            //                        d(b)   s(r)    => 待调整节点兄弟是黑色       p(b)    b     =>  平衡    p(r)    b
            //                              /   \                                /   \                    /   \
            //                             b     b                             d(b)   b                 d(b)   b
            //
            //                           p(b)                                       s(r)                     s(b)
            //                          /    \                                     /    \                   /    \
            //                        s(r)   d(b)    => 待调整节点兄弟是黑色        b    p(b)    =>  平衡     b    p(r)
            //                        /  \                                             /   \                    /   \
            //                       b    b                                           b    d(b)                b    d(b)
            // 2、删除节点有一个孩子：（传入参数修正时，删除节点已经被删除了，此时的待调整节点就是删剩下的节点形成的新树的根节点（后继节点））
            //                           p(b)
            //                         /      \
            //      删除前：           d(b)    s(r)
            //                          \      / \
            //                          r(b)  b   b
            //                          /\   / \ / \
            //                               b b b  b
            //                              /\ /\/\ /\
            //
            //                           p(b)
            //                         /      \
            //      删除后：           r(b)    s(r)
            //                        / \      / \
            //                                b   b
            //                               / \ / \
            //                               b b b  b
            //                              /\ /\/\ /\
            //
            //                            s(r)
            //                           /    \
            //                          p(b)   b
            //                         /  \   / \
            //       左旋后            r(b) b  b  b
            //                        / \ / \/ \/ \
            //                            b  b
            //                           / \/ \
            //
            //                            s(b)
            //                           /    \
            //                          p(r)   b
            //                         /  \   / \
            //      平衡后             r(b) b  b  b   （指的是加上被删除节点平衡）
            //                        / \ / \/ \/ \
            //                            b  b
            //                           / \/ \
            parent.color = Color.RED; // 原来的兄弟节点是红色，所以原来的父节点可定是黑色，那么旋转后要保证平衡，兄弟节点变黑，父节点变红
            sibling.color = Color.BLACK;
            fixDoubleBlack(node); // 再次调用进入兄弟节点为黑的情况
            return;
        }else {
            if (sibling != null) {
                // case 4: 删除节点是黑色，兄弟节点也是黑色，兄弟节点的左右孩子也是黑色
                if (isBlack(sibling.left) && isBlack(sibling.right)){
                    sibling.color = Color.RED; // 兄弟节点是黑色，兄弟节点左右孩子为黑，那么兄弟节点变红
                    if (isRed(parent)){
                        parent.color = Color.BLACK; // 如果父节点是红色，那么父节点变黑，就平衡了（右边也少了一个黑）
                    } else {
                        fixDoubleBlack(parent); // 如果父节点是黑色，也就是说以父节点为根节点的子树少一个黑色，这个子树中删除的就是少的黑色，删剩余的形成的根节点就是parent，那么递归调用parent，继续向上调整
                    }
                }
                // case 5: 删除节点是黑色，兄弟节点也是黑色，兄弟节点的左右孩子有红色
                else { // 兄弟节点孩子都为红也包含了
                    // LL
                    if (sibling.isLeftChild() && isRed(sibling.left)){ // 兄弟节点是左孩子，兄弟节点的左孩子是红色，那么就是LL情况
                        rightRotate(parent);
                        sibling.left.color = Color.BLACK; // 兄弟的左孩子由红色变黑色，因为换下来的父节点要变成黑色，保持平衡
                        sibling.color = parent.color; // 将换上去的兄弟节点和原来父节点的颜色一样，保持平衡
                    }
                    // LR
                    else if (sibling.isLeftChild() && isRed(sibling.right)){ // 兄弟节点是左孩子，兄弟节点的右孩子是红色，那么就是LR情况
                        sibling.right.color = parent.color; // 兄弟节点的右孩子改成原来父节点的颜色一样，因为左右旋后是该节点作为新父节点，保持平衡
                        leftRotate(sibling);
                        rightRotate(parent);
                    }
                    // RL
                    else if (!sibling.isLeftChild() && isRed(sibling.left)) {
                        sibling.left.color = parent.color; // 兄弟节点的左孩子改成原来父节点的颜色一样，因为左右旋后是该节点作为新父节点，保持平衡
                        rightRotate(sibling);
                        leftRotate(parent);
                    }
                    // RR
                    else {
                        leftRotate(parent);
                        sibling.right.color = Color.BLACK; // 兄弟的右孩子由红色变黑色，因为换下来的父节点要变成黑色，保持平衡
                        sibling.color = parent.color; // 将换上去的兄弟节点和原来父节点的颜色一样，保持平衡
                    }
                    parent.color = Color.BLACK; // 将换下来的parent的颜色变成黑色，保持平衡
                }
            }else { // sibling为null
                fixDoubleBlack(parent);
            }
        }
    }
}
